package own.stu.jobgib.playown.alg.solution.dp;

/**
 * 区间dp
 * <li/>给定一个序列/字符串，进行一些操作
 * <li/>最后一步会将序列/字符串去头/去尾
 * <li/>剩下的会是一个区间i,i
 * <li/>状态自然定义为fmiii表示面对子序列,...,j时的最优性质
 */
public class IntervalType {
    public static void main(String[] args) {
        IntervalType i = new IntervalType();

        // System.out.println(i.longestPalindromeSubseq("bbbab"));

        // System.out.println(i.firstWillWin(new int[]{3, 2, 2}));
        // System.out.println(i.firstWillWin(new int[]{1, 20, 4}));

        System.out.println(i.maxCoins(new int[]{3, 1, 5, 8}));
    }

    /**
     * 516. 最长回文子序列
     * 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
     * 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
     * <p>
     * 示例 1：
     * 输入：s = "bbbab"
     * 输出：4
     * 解释：一个可能的最长回文子序列为 "bbbb" 。
     */
    public int longestPalindromeSubseq(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        /*
        dp[i][j]表示区间（i，j)的子窜的最长回文子序列长度
        dp[i][j]
        max(
        dp[i - 1][j + 1] + 2(s[i-1] == s[j + 1])
        dp[i - 1][j]
        dp[i][j - 1]
        }

        初始化
        dp[0][0] == dp[1][1] = ...d[n-1][n-1] = 1;
         */
        int n = s.length();
        int[][] dp = new int[n][n];
        // len = 1;
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        // len = 2;
        for (int i = 0; i < n - 1; i++) {
            dp[i][i + 1] = (s.charAt(i) == s.charAt(i + 1)) ? 2 : 1;
        }

        //len = 3...n
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                if (s.charAt(i) == s.charAt(j))
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 2);
            }
        }
        return dp[0][n - 1];
    }

    /**
     * 396 · 硬币排成线 III (区间型动态规划，博弈型动态规划)
     * 有 n 个硬币排成一条线, 第 i 枚硬币的价值为 values[i].
     * 两个参赛者轮流从任意一边取一枚硬币, 直到没有硬币为止. 拿到硬币总价值更高的获胜.
     * 请判定 第一个玩家 会赢还是会输.
     * <p>
     * 样例
     * <p>
     * 输入: [3, 2, 2]
     * 输出: true
     * 解释: 第一个玩家在刚开始的时候拿走 3, 然后两个人分别拿到一枚 2.
     */
    public boolean firstWillWin(int[] values) {
        if (values == null || values.length == 0) {
            return false;
        }
        int n = values.length;
        /*
        该题的目标是先手拿到的价值高于后手
        假设先手的数字和为A, 后手为B 则 A >= B ==> A-B >=0
        那么先手和后手的数字差 SA = A - B, SB = B - A
        等价于
        先手让SA 最大化，后手让SB最大化
        当先手取走数字m, 那么 SA = -SB + m (-SB 是对手看起来的数字差的相反数）

        dp[i][j] 表示区间（i，j) 先手与后手的 硬币总价值之差的最大值
        dp[i][j] = max(-dp[i + 1][j] + v[i], -dp[i][j-1] + v[j])

        dp[0][0] = a[0]
         */
        int[][] dp = new int[n][n];
        // len = 1;
        for (int i = 0; i < n; i++) {
            dp[i][i] = values[i];
        }
        // len = 2...n
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(values[i] - dp[i + 1][j], values[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] >= 0;
    }

    /**
     * 312. 戳气球
     * 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
     * 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
     * 求所能获得硬币的最大数量。
     * <p>
     * 示例 1：
     * 输入：nums = [3,1,5,8]
     * 输出：167
     * 解释：
     * nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
     * coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
     */
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        /*
        这里正向模拟考虑很难
        反向思考，最后一个气球戳破，再次基础上，子问题就是最后一个气球两测作为一个区间，最多可以获得的金币数
        dp[i][j] 表示区间（i，j)中扎破气球的金币数最多
        dp[i][j] = max(dp[i][k] + dp[k][j] + a[i] * a[j] * a[k]) k = (i,j) 开区间
        初始值
        dp[0][1] = dp[1][2] ...= dp[n][n+1] = 0; //表示边界内无气球可以扎破
         */
        int n = nums.length;
        int[][] dp = new int[n + 2][n + 2];
        int[] arr = new int[n + 2];
        arr[0] = arr[n + 1] = 1;
        for (int i = 0; i < n; i++) {
            arr[i + 1] = nums[i];
        }

        //len = 2;
        /*
        可以不写
        for (int i = 0; i <= n; i++) {
            dp[i][i + 1] = 0;
        }*/
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len + 1;
                int multi = arr[i] * arr[j];
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][k] + dp[k][j] + multi * arr[k], dp[i][j]);
                }
            }
        }
        return dp[0][n + 1];
    }
}
